Thực đơn
Sắp xếp nổi bọt Mã giảprocedure bubble_sort1(list L, number n) //n=listsize For number i from n downto 2 for number j from 1 to (i - 1) if L[j] > L[j + 1] //nếu chúng không đúng thứ tự swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau endif endfor endforendprocedure
procedure bubble_sort2(list L, number n) //n=listsize For number i from 1 to n-1 for number j from n-1 downto i if L[j] > L[j + 1] //nếu chúng không đúng thứ tự swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau endif endfor endforendprocedure
Nếu trong một lần duyệt nào đó với một i cố định khi vòng lặp j kết thúc mà không cần phải đổi chỗ cặp phần tử nào, nghĩa là mọi cặp phần tử kề nhau đã đứng đúng thứ tự thì dãy đã được sắp xếp và không cần tiến hành vòng lặp tiếp theo. Do đó có thể dùng một cờ để kiểm soát việc này. Ta có một đoạn mã giả của thuật toán nổi bọt như sau:
procedure bubble_sort3(list L, number n) i:= n while i > 1 do has_swapped:= 0 //khởi tạo lại giá trị cờ for number j from 1 to (i - 1) if L[j] > L[j + 1] //nếu chúng không đúng thứ tự swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau has_swapped:= 1 //có đổi chỗ ít nhất một lần, danh sách chưa sắp xếp xong endif endfor if has_swapped = 0 //nếu không có lần đổi chỗ nào, danh sách đã sắp xếp xong exit else //nếu có ít nhất một lần đổi chỗ, danh sách chưa sắp xếp xong i = i - 1 endif enddoendprocedure
Ghi chú: Cũng có thể không cần dùng đến biến i, khi đó mỗi lần kiểm tra đều phải duyệt từ đầu đến cuối dãy.
Thực đơn
Sắp xếp nổi bọt Mã giảLiên quan
Tài liệu tham khảo
WikiPedia: Sắp xếp nổi bọt https://en.wikipedia.org/wiki/File:Bubble-sort-exa...